% Version control information:
%\svnid{$Id: vuelta_atras.tex 5 2009-03-29 23:59:23Z asalber $
%
\subsection{Vuelta atrás}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Técnica de vuelta atrás}
Al estudiar la técnica voraz vimos que esta no siempre permitía
llegar a la solución de un problema, porque las decisiones que se
tomaban en la construcción progresiva de la solución eran localmente
óptimas, lo que en muchas circunstancias no garantizaba llegar al óptimo global.

\medskip
La técnica de \textbf{vuelta atrás} intenta resolver este problema, y por tanto,
se parece a la técnica voraz en que resuelve un problema de manera gradual 
tomando decisiones o realizando acciones que permiten ir construyendo
progresivamente la solución del problema. Sin embargo, y a diferencia de la
técnica voraz, las decisiones tomadas pueden volverse a reconsiderar si no se
llega una solución aceptable u óptima. 

\medskip
Se suele aplicar también a problemas de decisión u optimización con o sin
restricciones, cuando no existe un criterio óptimo de toma de decisiones
locales.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Elementos de un problema de decisión}
Recordemos los elementos de un problema de decisión:
\begin{itemize}
\item \textbf{Función objetivo}: Es la función qu hay que minimizar o maximizar
y depende de las variables $x_1,\ldots, x_n$. 
\item \textbf{Dominio}: Es el conjunto de valores que pueden tomar las
variables. 
\item \textbf{Función solución}: Es la función que permite saber si unos
determinados valores de las variables son o no solución del problema. 
\item \textbf{Decisión}: Es la asignación de un valor a una variable.
\item \textbf{Restricciones}: Son las condiciones que deben cumplir las
soluciones. 
\item \textbf{Función factible}: Es la función que permite saber si una
solución cumple o no las restricciones.
\item \textbf{Solución en curso}: Es el conjunto de decisiones factibles
tomadas hasta el momento.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Espacio de búsqueda}
La solución del problema puede expresarse como una tupla $(x_1,\ldots,x_n)$ con
$x_i\in C_i$, siendo $C_i$ el dominio de $x_i$. Así pues, el número total de
posibles soluciones es $\prod_{i=1}^{n}k_i$, siendo $k_i$ el número de elementos
de $C_i$. 

\medskip
El conjunto de todas las posibles soluciones se conoce como \textbf{espacio de
búsqueda} y se representa como un árbol

\begin{center}
\psset{treesep=0.1cm,levelsep=1cm}
\newcommand{\dotedge}{\ncline[linestyle=dotted]}
\pstree[thislevelsep=0]{\Tn}{
\pstree[nodesep=0pt]{\Tp}{ 
	\pstree{\TR{$x_{11}$}}{
       \pstree[thislevelsep=1.5cm]{\TR{$x_{21}$}}{\psset{linestyle=dotted}
       			\pstree[thislevelsep=1.2cm]{\TR{}}{\psset{linestyle=solid}\TR{$x_{n1}$}\pstree{\Tfan[fansize=0.5cm,linestyle=dotted]}{}\TR{$x_{nk_n}$}}
       }
       \pstree{\Tfan[fansize=2cm,linestyle=dotted]}{}
       \pstree[thislevelsep=1.5cm]{\TR{$x_{2k_2}$}}{\psset{linestyle=dotted}
       			\pstree[thislevelsep=1.2cm]{\TR{}}{\psset{linestyle=solid}\TR{$x_{n1}$}\pstree{\Tfan[fansize=0.5cm,linestyle=dotted]}{}\TR{$x_{nk_n}$}}
       } 
    }
    \tspace{0.5cm}
    \pstree{\Tfan[fansize=3.6cm,linestyle=dotted]}{}
    \tspace{0.5cm}
    \pstree{\TR{$x_{1k_1}$}}{
       \pstree[thislevelsep=1.5cm]{\TR{$x_{21}$}}{\psset{linestyle=dotted}
       			\pstree[thislevelsep=1.2cm]{\TR{}}{\psset{linestyle=solid}\TR{$x_{n1}$}\pstree{\Tfan[fansize=0.5cm,linestyle=dotted]}{}\TR{$x_{nk_n}$}}
       }
       \pstree{\Tfan[fansize=2cm,linestyle=dotted]}{}
       \pstree[thislevelsep=1.5cm]{\TR{$x_{2k_2}$}}{\psset{linestyle=dotted}
       			\pstree[thislevelsep=1.2cm]{\TR{}}{\psset{linestyle=solid}\TR{$x_{n1}$}\pstree{\Tfan[fansize=0.5cm,linestyle=dotted]}{}\TR{$x_{nk_n}$}}
       } 
    }
    
}
\pstree[linestyle=none,nodesep=2pt,levelsep=1cm]{\TR{}}{
	\pstree{\TR{Nivel 1}}{
		\pstree[thislevelsep=1.5cm]{\TR{Nivel 2}}{
			\pstree[thislevelsep=1.2cm]{\TR{$\vdots$}}{\TR{Nivel $n$}}
		}
	}
}
}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Recorrido en profundidad del espacio de búsqueda}
Las soluciones se construyen partiendo de la raíz del espacio de búsqueda y
tomando decisiones realizando un recorrido exahustivo en profundidad del
mismo, lo cual garantiza la obtención de la solución global del problema.

\medskip
Se dice una solución en curso es \textbf{completable} si a partir de ella se
puede alcanzar la solución del problema. 

\medskip
Mientras que la técnica de fuerza bruta recorrería todo el espacio de búsqueda,
lo que supondría un coste exponencial, la técnica de vuelta atrás, cuando llega
a una solución no completable, da \emph{marcha atrás} y busca por otro camino
del espacio de búsqueda, evitando así recorrer todo el subárbol que queda por
debajo de dicha solución no completable.    
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Diferentes versiones del algoritmo con vuelta atrás}
Dependiendo del tipo de problema que tengamos que resolver existen diferentes
formas de aplicar la vuelta atrás: 
\begin{itemize}
\item \textbf{Vuelta atrás para una solución}: El
algoritmo recorre el espacio de búsqueda  hasta que encuentra la primera
solución. Es el más sencillo.
\item \textbf{Vuelta atrás para todas las soluciones}: El
algoritmo recorre el espacio de búsqueda guardando todas las soluciones que
encuentra hasta que ya no haya más. 
\item \textbf{Vuelta atrás para la mejor solución}: El
algoritmo recorre el espacio de búsqueda comparando cada solución que encuentra
con la mejor solución obtenida hasta el momento, y quedándose con la mejor.
Cuando ya no hay más soluciones, devuelve la mejor encontrada. Suele aplicarse
a problemas de optimización.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Algoritmo de vuelta atrás para todas las soluciones}
El siguiente algoritmo calcula todas las soluciones de un problema con la
técnica de vuelta atrás
\begin{lstlisting}
funcion vuelta_atras(entero i, T sol[n], conjunto<T> C)
  para_todo x en C
    sol[i] = x
    si completable(sol,i) entonces
      si solucion(sol) entonces
        guardar(sol)
      fin_si
      si (i<n) entonces
        vuelta_atras(i+1,sol,C)
      fin_si
    fin_si
  fin_para_todo
fin_funcion
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Poda del espacio de búsqueda}
El algoritmo anterior no genera el espacio de búsqueda de forma explícita, sino
implícitamente mediante llamadas recursivas. 

\medskip
Cuando se llega a una solución en curso no completable, no se realizan más
llamadas recursivas y por tanto no se construye el subárbol correspondiente del
espacio de búsqueda. Esto se conoce como \textbf{poda} del espacio de búsqueda.

\medskip
La poda es un mecanismo que permite descartar del recorrido ciertas zonas del
espacio de búsqueda, bien porque allí no haya soluciones, bien porque ninguna
de las soluciones de esas zonas es la óptima.  

\medskip
Cuanto mayor sea el número de nodos podados, más eficiente será la búsqueda de
soluciones. 
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste temporal del algoritmo de vuelta atrás}
El coste temporal de un algoritmo que utilice la técnica de vuelta atrás, suele depender de:
\begin{itemize}
\item El número de nodos del espacio de búsqueda que se visitan $v(n)$.
\item El coste de las funciones solucion y completable en cada nodo $p(n)$.
\end{itemize}
En total $O(p(n)v(n))$.

\medskip
Si se consigue que la función completable pode muchos nodos, el tamaño
de $v(n)$ se puede reducir drásticamente: 
\begin{itemize}
\item Si se reduce a un solo nodo (solución voraz) tendremos un coste
$O(p(n)n)$. 
\item Por el contrario, en el peor de los casos (solución por fuerza bruta),
tendremos un coste $O(p(n)kn)$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplos de vuelta atrás}
Algunos problemas conocidos que pueden resolverse mediante la técnica de vuelta atrás:
\begin{itemize}
\item El problema de las ocho reinas.
\item La suma de subconjuntos.
\item El problema de la mochila entera.
\item El problema del coloreado de grafos.
\item La búsqueda de ciclos Hamiltonianos en grafos.
\item El recorrido de un laberinto.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del coloreado de grafos}
Se dispone de un grafo $G$ y de $k$ colores. ¿Es posible colorear los vértices
de $G$ de manera que no haya dos vértices adyacentes  con el mismo color? 

\medskip
Otro famoso problema reducible a este es el del coloredado de mapas. ¿Puede
pintarse un mapa de manera que no haya dos regiones adyacentes con el mismo
color, utilizando $k$ colores? 

\medskip
Cada región se representa como un vértice del grafo y si dos regiones son
adyacentes, sus respectivos vértices de conectan con una arista.   
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coloreado de grafos}
\framesubtible{Espacio de búsqueda}
Si el grafo tiene $n$ vértices, representaremos el color de cada vértice en un
vector \texttt{color[$n$]=\{$c_1,\ldots,c_n$\}} siendo, $c_i\in\{1,\ldots,k\}$
el color del vértice $i$. 

\medskip
El espacio de búsqueda asociado tiene $k^n$ posibles soluciones. Por
ejemplo, para $n=3$ y $k=3$ se tiene el siguiente espacio de búsqueda con 27
posibles soluciones.

\begin{center}
\scalebox{0.65}{
\psset{treesep=0.05cm,levelsep=1cm}
\pstree[thislevelsep=0]{\Tn}{
\pstree[nodesep=0pt]{\Tp}{ 
	\pstree{\Tcircle[fillstyle=solid,fillcolor=blue]{1}}{
       \pstree{\Tcircle[fillstyle=solid,fillcolor=blue]{1}}{
       		\Tcircle[fillstyle=solid,fillcolor=blue]{1}
       		\Tcircle[fillstyle=solid,fillcolor=green]{2}
       		\Tcircle[fillstyle=solid,fillcolor=red]{3}
       }
       \pstree{\Tcircle[fillstyle=solid,fillcolor=green]{2}}{
       		\Tcircle[fillstyle=solid,fillcolor=blue]{1}
       		\Tcircle[fillstyle=solid,fillcolor=green]{2}
       		\Tcircle[fillstyle=solid,fillcolor=red]{3}
       }
       \pstree{\Tcircle[fillstyle=solid,fillcolor=red]{3}}{
       		\Tcircle[fillstyle=solid,fillcolor=blue]{1}
       		\Tcircle[fillstyle=solid,fillcolor=green]{2}
       		\Tcircle[fillstyle=solid,fillcolor=red]{3}
       }
    }
    \pstree{\Tcircle[fillstyle=solid,fillcolor=green]{2}}{
       \pstree{\Tcircle[fillstyle=solid,fillcolor=blue]{1}}{
       		\Tcircle[fillstyle=solid,fillcolor=blue]{1}
       		\Tcircle[fillstyle=solid,fillcolor=green]{2}
       		\Tcircle[fillstyle=solid,fillcolor=red]{3}
       }
       \pstree{\Tcircle[fillstyle=solid,fillcolor=green]{2}}{
       		\Tcircle[fillstyle=solid,fillcolor=blue]{1}
       		\Tcircle[fillstyle=solid,fillcolor=green]{2}
       		\Tcircle[fillstyle=solid,fillcolor=red]{3}
       }
       \pstree{\Tcircle[fillstyle=solid,fillcolor=red]{3}}{
       		\Tcircle[fillstyle=solid,fillcolor=blue]{1}
       		\Tcircle[fillstyle=solid,fillcolor=green]{2}
       		\Tcircle[fillstyle=solid,fillcolor=red]{3}
       }
    }
    \pstree{\Tcircle[fillstyle=solid,fillcolor=red]{3}}{
       \pstree{\Tcircle[fillstyle=solid,fillcolor=blue]{1}}{
       		\Tcircle[fillstyle=solid,fillcolor=blue]{1}
       		\Tcircle[fillstyle=solid,fillcolor=green]{2}
       		\Tcircle[fillstyle=solid,fillcolor=red]{3}
       }
       \pstree{\Tcircle[fillstyle=solid,fillcolor=green]{2}}{
       		\Tcircle[fillstyle=solid,fillcolor=blue]{1}
       		\Tcircle[fillstyle=solid,fillcolor=green]{2}
       		\Tcircle[fillstyle=solid,fillcolor=red]{3}
       }
       \pstree{\Tcircle[fillstyle=solid,fillcolor=red]{3}}{
       		\Tcircle[fillstyle=solid,fillcolor=blue]{1}
       		\Tcircle[fillstyle=solid,fillcolor=green]{2}
       		\Tcircle[fillstyle=solid,fillcolor=red]{3}
       }
    }
}
\pstree[linestyle=none,nodesep=2pt]{\TR{}}{
	\pstree{\TR{Vértice 1}}{
		\pstree{\TR{Vértice 2}}{
			\TR{Vértice 3}
		}
	}
}
}
}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Coloreado de grafos}
\framesubtitle{Algoritmo con vuelta atrás}
La siguiente función en C++ resuelve el problema del coloreado de grafos con la
técnica de vuelta atrás: 
\begin{lstlisting}
/** colorea.cpp
* n numero de vertices
* k numero de colores
* ady matriz de adyacencia
* color vector solucion con los colores de cada vertice
* i vertice actual 
*/
void colorea(int n, int k, bool **ady, int *color, int i){
  for (int j=0; j<k; j++){
    color[i]=j;
    if (completable(ady, color, i))
      if (i==n-1) imprimir(n, color);
      else colorea(n, k, ady, color, i+1);
  }
 return;
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Coloreado de grafos}
\framesubtitle{Función completable}
Donde la función completable chequea la factibilidad de la solución comprobando
que el color asignado al vétice $i$ no es el mismo que el de otro vértice
adyacente.  
\begin{lstlisting}
/** completable.cpp
* ady matriz de adyacencia
* color vector solucion con los colores de cada vertice
* i vertice actual 
*/
bool completable(bool **ady,int *color, int i){
  int j=0;
  for (int j=0;j<i;j++)
    if (adj[j][i] && color[j]==color[i]) return false;
  return true;
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coloreado de grafos}
\framesubtitle{Ejemplo con la técnica de vuelta atrás}
Aplicando el algoritmo anterior al siguiente mapa
\[
\includegraphics[scale=0.6]{img/mapa}
\qquad
\raisebox{0.9cm}{
Ady =\left(
\begin{array}{ccccc} 
0 & 1 & 1 & 1 & 0\\
1 & 0 & 1 & 0 & 1\\
1 & 1 & 0 & 1 & 1\\
1 & 0 & 1 & 0 & 1\\
0 & 1 & 1 & 1 & 0
\end{array}
\right)
}
\]
con tres colores \textcolor{blue}{1}, \textcolor{green}{2} y
\textcolor{red}{3}, se obtienen seis posibles soluciones
\begin{center}
\includegraphics[scale=0.6]{img/mapacoloreado}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Algoritmo de vuelta atrás para la mejor solución}
El siguiente algoritmo calcula la mejor solución de un problema de optimización
con la técnica de vuelta atrás 
\begin{lstlisting}
funcion vuelta_atras(entero i, T sol[n], conjunto<T> C)
  para_todo x en C
    sol[i] = x
    si (completable(sol,i) && coste(sol,i)) < mcoste entonces
      si solucion(sol) entonces
        mejor_solucion = sol
        mcoste = coste(sol,i)
      fin_si
      si (i<k) entonces
        vuelta_atras(i+1, sol)
      fin_si
    fin_si
  fin_para_todo
fin_funcion
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Poda basada en la mejor solución}
Cuando estemos ante un problema de optimización, al recorrer el espacio de
búsqueda, además de la poda que realiza la función completable, podemos realizar
otra poda basada en el coste de la mejor solución en curso.

\medskip
La idea es que una solución en curso se poda cuando, a pesar de ser 
completable, no es posible conseguir una solución mejor que la mejor solución
en curso, aún cuando se genere todo el subárbol del espacio de búqueda que
cuelga de ella (\texttt{coste(sol,i)$\geq$mejorcoste}).  

\medskip
Como antes, esta poda es más efectiva cuantos más nodos consiga eliminar, por
lo que interesa encontrar una solución próxima a la solución óptima cuanto
antes (se puede utilizar una estrategia voraz para ello).
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila entera}
\framesubtible{Ejemplo de vuelta atrás}
El problema de la mochila entera también puede resolverse mediante la técnica
de vuelta atrás. 

\medskip
Si tenemos $n$ objetos y representamos el contenido de la mochila con un
vector \texttt{sol[$n$]=\{$x_1,\ldots,x_n$\}} donde
\[
x_i = 
\begin{cases}
0 & \mbox{si el objeto $i$ no está en la mochila}\\
1 & \mbox{si el objeto $i$ si está en la mochila}
\end{cases}
\]
entonces el espacio de búsqueda asociado es
\begin{center}
\psset{treesep=0.2cm,levelsep=0.5cm,nodesep=1pt}
\newcommand{\dotedge}{\ncline[linestyle=dotted]}
\pstree[thislevelsep=0]{\Tn}{
\pstree{\Tp}{ 
	\pstree{\TR{0}}{
       \pstree{\TR{0}}{\psset{linestyle=dotted}
       			\pstree{\TR{}}{\psset{linestyle=solid}\TR{0}\TR{1}} 
       }
       \tspace{0.5cm}
       \pstree{\TR{1}}{\psset{linestyle=dotted}
       			\pstree{\TR{}}{\psset{linestyle=solid}\TR{0}\TR{1}} 
       }
    }
    \tspace{2cm}
    \pstree{\TR{1}}{
       \pstree{\TR{0}}{\psset{linestyle=dotted}
       			\pstree{\TR{}}{\psset{linestyle=solid}\TR{0}\TR{1}} 
       }
       \tspace{0.5cm}
       \pstree{\TR{1}}{\psset{linestyle=dotted}
       			\pstree{\TR{}}{\psset{linestyle=solid}\TR{0}\TR{1}} 
       }
    }
    
}
\tspace{0.5cm}
\pstree[linestyle=none]{\TR{}}{
	\pstree{\TR{Objeto 1}}{
		\pstree{\TR{Objeto 2}}{
			\pstree{\TR{$\vdots$}}{\TR{Objeto $n$}}
		}
	}
}
}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila}
\feramesubtitle{Poda basada en la mejor solucion}
Para poder aplicar la poda basada en la mejor solución resulta útil disponer de
una función \texttt{cota(sol,i)} que calcule una cota superior del valor de la
mochila en las soluciones que pueden obtenerse a partir de la solución en curso.  

\medskip
Con esta función, si \texttt{maxval} el máximo valor de la mochila encontrado
hasta el momento, cada vez que $\texttt{cota(sol,i) < maxval}$ podaremos el
subárbol del espacio de búsqueda que cuelgue de dicha solución en curso y
haremos la vuelta atrás. 

\medskip
En nuestro caso, resulta fácil obtener una cota mediante el
algoritmo voraz para el problema de la mochila fraccionada.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Algoritmo con vuelta atrás}
La siguiente función en C++ resuelve el problema de la mochila entera con la
técnica de vuelta atrás:
\begin{lstlisting}
/** mochila_entera.cpp
* n es el numero de objetos
* peso el vector de pesos y valor el de valores de los objetos
* sol es el vector con los objetos que entran en la mochila
* valact es el valor actual de la mochila y pesact su peso 
* mejorsol es el vector con mejor solucion hasta el momento
* maxval es el valor de la mochila para la mejor solucion
* i es el objeto actual sobre el que se debe tomar la decision
*/
void llenar(int n,float *peso,float * valor,int *sol, 
  float valact,float pesact,int *mejorsol,float &maxval,int i){
  float tval, tpeso;            
  for (int j=1;j>=0;j--){
    sol[i] = j;
    tval = valact + j*valor[i]; tpeso = pesoact - j*peso[i];
    if (tpeso>=0 && maxval<cotaval(tval, tpeso, i+1)) //PODA
      if (i<n-1)
        llenar(n,peso,valor,sol,tval,tpeso,mejorsol,maxval,i+1);
      else {maxvalue = tempvalue; copiar(sol, bestsol);}
  } }
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila entera}
\framesubtitle{Función de cota del valor máximo}
Donde la función de cota es la siguiente:
\begin{lstlisting}
/** mochila_entera.cpp
* n es el numero de objetos
* peso el vector de pesos y valor el de valores de los objetos
* tval es el valor actual de la mochila 
* tpeso es la capacidad actual de la mochila
* i es el objeto actual
*/
float cotaval(int n, float *peso, float *valor, 
              float tval, float tpeso, int i){
  for (int j=i;j<n;j++)
    if (peso[j] > tpeso)
      return tval + tpeso/peso[j]*valor[j];
    else {
      tval += valor[j]; tpeso -= peso[j]; }
  return tval;
}
\end{lstlisting}
Esta función utiliza la técnica voraz del problema de la mochila fraccionada y
por tanto se necestia que los objetos estén ordenados en orden decreciente por
valor/peso.  
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila entera}
\framesubtitle{Ejemplo con la técnica de vuelta atrás}
Si hay 5 objetos de valores \texttt{valor[]=\{30,40,60,10,20\}} y pesos
\texttt{peso[]=\{6,10,20,5,15\}}, y una mochila de capacidad 30, entonces la
función realiza el siguiente recorrido del espacio de búsqueda:  
\begin{center}
\psset{treesep=0.15cm,levelsep=0.9cm,nodesep=1pt}
\pstree[thislevelsep=0]{\Tn}{
\pstree{\Tp}{ 
	\pstree{\TR{1}}{
       \pstree{\TR{1}}{
       		\pstree[linestyle=dashed,linecolor=red]{\TR{1}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			}
			\pstree{\TR{0}}{
				\pstree{\TR{1}}{\TR{1}\pstree[levelsep=0.5cm,linecolor=green,arrows=->]{\TR{0}}{\TR{\textcolor{green}{80}}}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			} 
       }
       \pstree{\TR{0}}{
       		\pstree{\TR{1}}{
				\pstree[linestyle=dashed,linecolor=red]{\TR{1}}{\TR{1}\TR{0}}			
				\pstree{\TR{0}}{\TR{1}\pstree[levelsep=0.5cm,linecolor=green,arrows=->]{\TR{0}}{\TR{\textcolor{green}{90}}}} 
			} 
			\pstree[linestyle=dashed,linecolor=orange]{\TR{0}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			} 
       }
    }
    \pstree{\TR{0}}{
       \pstree{\TR{1}}{
       		\pstree{\TR{1}}{
				\pstree[linestyle=dashed,linecolor=red]{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\pstree[levelsep=0.5cm,linecolor=green,arrows=->]{\TR{0}}{\TR{\textcolor{green}{100}}}}
			}
			\pstree[linestyle=dashed,linecolor=orange]{\TR{0}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			} 
       }
       \pstree[linestyle=dashed,linecolor=orange]{\TR{0}}{
       		\pstree{\TR{1}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			}
			\pstree{\TR{0}}{
				\pstree{\TR{1}}{\TR{1}\TR{0}}
				\pstree{\TR{0}}{\TR{1}\TR{0}}
			} 
       }
    }
} 
\tspace{0.1cm}
\pstree[linestyle=none]{\TR{}}{ \footnotesize
	\pstree{\TR{\parbox{1.5cm}{Objeto 1\\ p=6,v=30}}}{
		\pstree{\TR{\parbox{1.5cm}{Objeto 2\\ p=10,v=40}}}{
			\pstree{\TR{\parbox{1.5cm}{Objeto 3\\ p=20,v=60}}}{
				\pstree{\TR{\parbox{1.5cm}{Objeto 4\\ p=5,v=10}}}{
					\pstree[levelsep=0.5cm]{\TR{\parbox{1.5cm}{Objeto 5\\ p=15,v=20}}}{
						\TR{maxval}
					} 
				}
			}
		}
	}
}
}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Mejoras de la vuelta atrás}
\begin{itemize}
\item Una posible mejora sería comenzar buscando una solución factible por algún
procedimiento rápido (normalmente voraz), e inicializar el valor de la mejor
solución con el valor de dicha solución. De esta manera, la poda basada en mejor solución comenzaría
a funcionar antes.   

\item Otra posible mejora consiste en guardar para cada variable $x_i$ la lista
de los valores de su dominio $C_i$: 
\begin{itemize}
\item Cada vez que se asigna un valor a una variable, se eliminan de todas las
variables no asignadas los valores incompatibles con la asignación. Esto reduce
el espacio de búsqueda aunque también supone un coste.  
\item Si a alguna variable no le quedan valores posibles, entonces no es posible la
solución y se hace vuelta atrás.
\end{itemize}
\item Por último, está la posibilidad realizar un recorrido
dinámico (no necesariamente en profundidad) del espacio de
búsqueda (esto lo utiliza la técnica de ramificación y poda).
\end{itemize}  
\end{frame}
